package 中等.搜索.深度优先搜索;

import util.TreeNode;

/**
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * 有效 二叉搜索树定义如下：
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/validate-binary-search-tree
 */
public class 验证二叉搜索树_98 {

    public static void main(String[] args) {

        System.out.println(true && true && false);

    }

    /**
     * 中序遍历是一个递增的序列
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        return !isNotBST(root);
    }

    private long preNum = Long.MIN_VALUE;

    public boolean isNotBST(TreeNode root) {
        if (root == null) {
            return false;
        }
        boolean leftNot = isNotBST(root.left);
        if (preNum >= root.val) {
            return true;
        }
        preNum = root.val;
        boolean rightNot = isNotBST(root.right);
        // 只有有一个节点不符合条件，返回 true
        return leftNot || rightNot;
    }

}
